package study.search;

import java.util.ArrayList;
import java.util.Arrays;

public class BinarySearch {
    public static void main(String[] args) {
//        int[] arr = {2, 3, 66, 992, 1028, 3923};
//        int find = binarySearch(arr, 0, arr.length - 1, 3);
//        System.out.println(find);

        int[] arr = {2, 3, 66, 66, 66, 992, 1028, 3923};
        ArrayList<Integer> indexes = binarySearch2(arr, 0, arr.length - 1, 66);

        System.out.println(indexes);

    }

    /**
     * 基本的二分法查找
     * @param arr
     * @param left
     * @param right
     * @param findValue
     * @return
     */
    public static int binarySearch(int[] arr, int left, int right, int findValue){
        //没有找到的情况
        if (left > right){
            return -1;
        }

        //获取中间值和中间索引
        int midIndex = (left + right) / 2;
        int midValue = arr[midIndex];

        //判断
        if (findValue < midValue){
            return binarySearch(arr, left, midIndex - 1, findValue);
        }else if (findValue > midValue){
            return binarySearch(arr, midIndex + 1, right, findValue);
        }else {
            return midIndex;
        }

    }

    /**
     * 改进的二分法查找，如果有多个相同的数字，则返回一个下标集合
     * @param arr
     * @param left
     * @param right
     * @param findValue
     * @return
     */
    public static ArrayList<Integer> binarySearch2(int[] arr, int left, int right, int findValue){
        //没有找到的情况
        if (left > right){
            return new ArrayList<>();
        }

        //获取中间值和中间索引
        int midIndex = (left + right) / 2;
        int midValue = arr[midIndex];

        //判断
        if (findValue < midValue){
            return binarySearch2(arr, left, midIndex - 1, findValue);
        }else if (findValue > midValue){
            return binarySearch2(arr, midIndex + 1, right, findValue);
        }else {
            //找到值

            //定义一个List，接收下标集合
            ArrayList indexList = new ArrayList<Integer>();

            //扫描左边
            int temp = midIndex - 1;
            while (true){
                //先考虑退出条件
                //因为二分查找法的数组是有序的，所以可以使用 arr[temp] != findValue 判断
                if (temp < 0 || arr[temp] != findValue){
                    break;
                }
                indexList.add(temp);
                temp--;
            }

            //把中间的添加到集合
            indexList.add(midIndex);

            //扫描右边
            temp = midIndex + 1;
            while (true){
                //先考虑退出条件
                //因为二分查找法的数组是有序的，所以可以使用 arr[temp] != findValue 判断
                if (temp > arr.length - 1 || arr[temp] != findValue){
                    break;
                }
                indexList.add(temp);
                temp++;
            }

            //返回下标集合
            return indexList;
        }

    }

}
